package com.mamingchao.foundation.arraysort.buckesort.radixsort;

import com.mamingchao.foundation.arraysort.Sortable;

import java.util.Objects;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 基数排序，是桶排序的一种
 * 第一步，基于桶排序思想，按数组里数字的个位排序；
 *    0    1    2   3    4    5     6
 * |    |    |    |    |    |    |     |
 * |    |    |    |    |    |    |     |
 *
 * 第二步，按十位数字，对原数组进行桶排序
 * ......以此类推；比如，数组里数字最长是5位，那么就递归执行5次
 *
 * 这是自己实现的；最初用二维数组实现，但是空间复杂度有点高，所有后来放弃里
 * 因为如果用二维数组，第二层数组 每个都得初始化长度，长度都需要是arr.length
 *
 * LSD 的实现
 *
 * Created by mamingchao on 2021/6/10.
 */
public class RadixSortImpl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {
        // 第一步，按照原数字的个位大小，做一个桶排序
        int numMaxLength = 0;
        LinkedBlockingQueue<Integer>[] bucket = new LinkedBlockingQueue[10];
        for (int i = 0; i < arr.length; i++) {
            //通过第一次遍历，获取数组 所有num 最长的长度值
            int originalNumLength = String.valueOf(arr[i]).length();
            if (originalNumLength > numMaxLength) {
                numMaxLength = originalNumLength;
            }

            this.putNumIntoBucketFromArr(arr[i],1,bucket);
        }

        this.getSortedNumFromBucket(arr,bucket);

        // 循环十位，百位。。。
        for (int i = 1; i < numMaxLength; i++) {
            //生成model
            int model = 1;
            for (int j = 0; j < i; j++) {
                model *=10;
            }

            for (int j = 0; j < arr.length ; j++) {
                this.putNumIntoBucketFromArr(arr[j],model,bucket);
            }

            this.getSortedNumFromBucket(arr,bucket);
        }
    }

    /**
     * 把array 里的值，根据指定位的值大小，放进指定的桶里
     * @param currentNum
     * @param model
     * @param bucket
     */
    private void putNumIntoBucketFromArr(int currentNum, int model, LinkedBlockingQueue<Integer>[] bucket) {
        int targetNum = GenereteDigitNumUtil.getSingleNum(currentNum,model);
        // 循环操作，从十位 -》 千位，万位。。。
        // num的个位的值 ，即为
        LinkedBlockingQueue<Integer> currentBucket;
        if (Objects.isNull(bucket[targetNum])) {
            currentBucket = new LinkedBlockingQueue<>();
        } else {
            currentBucket = bucket[targetNum];
        }
        currentBucket.offer(currentNum);
        bucket[targetNum] = currentBucket;
    }

    /**
     * 把桶里的数 按顺序 拿出来，放回数组中
     * @param arr
     * @param bucket
     */
    private void getSortedNumFromBucket(int[] arr, LinkedBlockingQueue<Integer>[] bucket) {
        int index = 0;
        for (int k = 0; k < 10; k++) {
            LinkedBlockingQueue<Integer> currentBucket = bucket[k];
            if (currentBucket == null) {
                continue;
            }

            int loopNum = currentBucket.size();
            for (int j = 0; j < loopNum; j++) {
                arr[index ++] = currentBucket.poll();
            }
        }
    }

}
